package com.jia.explore.dynamicprogramming.knapsack;

import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Stream;

/**
 * @program: Leetcode
 * @description: 01背包 https://www.acwing.com/problem/content/2/
 * @author: STU756
 * @create: 2020-08-10 16:47
 */
public class Dy_01Knapsack {
    private static final int N = 30;

    public static void main(String[] args) {
        int[] v = new int[N];//物品种类
        int[] w = new int[N];//物品价值
        //输入数据
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); //物品个数
        int m = scanner.nextInt(); //总体积
        int count = 1;
        while (count <= n) {
            v[count] = scanner.nextInt();
            w[count] = scanner.nextInt();
            count++;
        }
        /*
         *  f[i][j]表示只看前i个物体，总体之为j的情况下，总价值最大是多少
         *   result = max[f[n][0~v]
         * f[i][j]:
         * 1.不选第i个物品，f[i][j] = f[i-1][j]
         * 2.选第i个物品, f[i-1][j-v[i]]+w[i]
         *  f[i][j] = max{1, 2}
         * f[0][0] = 0    初始化
         */

        int[][] f = new int[N][N];
        //初始化
        f[0][0] = 0;
        for (int j = 1; j <= n; j++) {
//            for(int k = 1; k < v[j]; k++) {
//                f[j][k] = f[j-1][k];
//            }
//            for (int k = v[j]; k <= m; k++) {
//                f[j][k] = Math.max(f[j-1][k], f[j - 1][k - v[j]] + w[j]);
//            }
            for(int k = 1; k < v[j]; k++) {
                f[j][k] = f[j-1][k];
            }
            for(int k = v[j]; k <= m; k++) {
                f[j][k] = Math.max(f[j-1][k], f[j][k-v[j]] + w[j]);
            }
            System.out.println(Arrays.toString(f[j]));
        }
        int max = 0;
        for (int j = 0; j <= m; j++) {
            max = Math.max(f[n][j], max);
        }
        print(f);
        System.out.println(max);

        int[] f2 = new int[N]; //f[m]表示小于等于体积为m的最大值是多少
        //对f[n][m]进行状态压缩
        for (int i = 1; i <= n; i++) {
            //逆循环，会把dp[j]不会把j前面上一场的值覆盖掉
            for (int j = m; j >= v[i]; j--) {
                f2[j] = Math.max(f2[j], f2[j - v[i]] + w[i]);
            }
            System.out.println(Arrays.toString(f2));
        }
        System.out.println(f[m]);


        System.out.println("---------------------------------------------");
        int[][] dp2 = new int[N][N];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp2[i], Integer.MIN_VALUE);
        }
        dp2[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= v[i]; j--) {
                dp2[i][j] = Math.max(dp2[i - 1][j], dp2[i - 1][j - v[i]] + w[i]);
            }
            System.out.println(Arrays.toString(dp2[i]));
        }

    }

    private static void print(int[][] dp) {
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
    }
}
